#ifndef EQUIVALENCE_HPP_
#define EQUIVALENCE_HPP_
namespace quadil{
namespace __equivalence__{
	class IntListNode{
	public:
		int val;
		IntListNode* next;
		IntListNode(int v){val=v;next=0;}
		~IntListNode(){if(next){next->~IntListNode();delete next;next=0;}}
		int inList(int v){
            if(val==v)return 1;
            if(next==0)return 0;
            return next->inList(v);
		}
		friend class IntList;
		friend class EquivalenceSets;
	};
	class IntList{
	public:
		IntListNode* head;
		IntListNode* tail;
		int nbElem;
		int setCode;
		IntList(int firstVal){
				this->setCode=-1;
				this->head=new IntListNode(firstVal);
				this->tail=this->head;
				this->nbElem=1;
		}
		void stealAllNodes(IntList* l){
				if(l->nbElem){
						if(this->nbElem){
								this->nbElem+=l->nbElem;
								this->tail->next=l->head;
								this->tail=l->tail;
								l->head=0;
								l->tail=0;
						}else{
								this->head=l->head;
								this->tail=l->tail;
								this->nbElem=l->nbElem;
								l->tail=0;
								l->head=0;
								l->nbElem=0;
						}
				}
		}
		int has(int v){
				return head->inList(v);
		}
		void print(){
				std::cout<<"{";
				for(IntListNode* p=this->head;p;p=p->next){
						std::cout<<p->val<<" ";
				}
				std::cout<<"}\n";
		}
		virtual ~IntList(){delete this->head;}
		friend class EquivalenceSets;
	};
	class EquivalenceSets{
	public:
		typedef std::map<int,IntList*> ListMap;
		ListMap listMap;
		std::vector<IntList*> listVector;
		std::map<int,int> compiledMap;
		t_label nextAvailableLabel;
		EquivalenceSets(){nextAvailableLabel=100000000;}/*mustBe greater than max num of conn components*/
		int getNewCode(){
				this->listVector.push_back(new IntList(nextAvailableLabel++));
				this->listMap[nextAvailableLabel-1]=listVector.back();
				return nextAvailableLabel-1;
		}
		void setEquivalent(int num1,int num2){
				if(this->listMap[num1]!=this->listMap[num2]){
						IntList *l_erase=this->listMap[num2];
						IntList *l_update=this->listMap[num1];
						for(IntListNode* p=l_erase->head;p;p=p->next){
								this->listMap[p->val]=l_update;
						}
						l_update->stealAllNodes(l_erase);
				}
		}
		void finalize(){
				this->assignLabels();
				this->createMap();
				this->clearLists();

		}
		int operator[](int v){
				return this->compiledMap[v];
		}
		virtual ~EquivalenceSets(){
				this->clearLists();
				this->compiledMap.clear();
		}
		void assignLabels(){
				int curLabel=1;
				for(unsigned int i=0;i<this->listVector.size();i++){
						if(listVector.at(i)->nbElem>0){
								listVector.at(i)->setCode=curLabel++;
						}
				}
		}
		void createMap(){
				for(std::map<int,IntList*>::iterator iter =this->listMap.begin();iter!=listMap.end();++iter){
						this->compiledMap[iter->first]=iter->second->setCode;
				}
		}
		void clearLists(){
				this->listMap.clear();
				for(unsigned int i=0;i<this->listVector.size();i++){
						delete this->listVector.at(i);
				}
				this->listVector.clear();
		}
	};
}
}
#endif /*EQUIVALENCE_HPP_*/
